package bfs;

import java.util.LinkedList;
import java.util.Queue;

public class 接雨水2 {

    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        int[] dirs = {-1,0,1,0,-1};
        int maxHeight = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxHeight = Math.max(maxHeight,heightMap[i][j]);
            }
        }
        int[][] water = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                water[i][j] = maxHeight;
            }
        }
        //存的是边界的 x,y值
        Queue<int[]> qu = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //边界
                if (i==0 || i==m-1 || j==0 || j==n-1){
                    if (water[i][j]>heightMap[i][j]) {
                        water[i][j] = heightMap[i][j];
                        qu.offer(new int[]{i, j});
                    }
                }
            }
        }
        while (!qu.isEmpty()){
            int[] curr = qu.poll();
            int x = curr[0];
            int y = curr[1];
            for (int i = 0; i < 4; i++) {
                //上下左右
                int nx = x+dirs[i],ny = y+dirs[i+1];
                if (nx<0 || nx>=m || ny<0 || ny>=n)
                    continue;
                //
                if (water[x][y] < water[nx][ny] && water[nx][ny]>heightMap[nx][ny]){
                    water[nx][ny] = Math.max(water[x][y], heightMap[nx][ny]);
                    qu.offer(new int[]{nx, ny});
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res += water[i][j] - heightMap[i][j];
            }
        }
        return res;
    }

}
